Análise de Estruturas de Dados e Algoritmos em Python (2ª Edição): Modelagem em Teoria dos Grafos: Do Mundo Real para Estruturas de Dados Abstratas

A modelagem em teoria dos grafos é o processo de abstrair relações complexas do mundo real (como roteamento na internet ou transições de estado) em objetos matemáticos $G = (V, E)$. Definindo entidades comovértices (vértice) e as relações comoarestas (aresta)podemos utilizar tipos de dados abstratos (ADT) e algoritmos unificados para resolver uma variedade de problemas.

Definição dos Componentes Principais

vértices (vértice): Também conhecidos como nós. Possuem uma "chave" (Key) como identificador único e podem carregar um "payload" (carga útil).
arestas (aresta): Conecta dois vértices, indicando que existe uma relação entre eles. Pode ser unidirecional (grafo direcionado) ou bidirecional.
peso (peso): 边上的数值，代表成本（如距离、延迟、带宽）。

Precisão Matemática

Matematicamente, $G = (V, E)$. Onde $V$ é o conjunto de vértices e $E$ é o conjunto de pares ordenados $(v, w)$ que formam as arestas, com $v, w \in V$. Essa estrutura altamente abstrata permite usar os mesmos algoritmos BFS/DFS para resolver desde navegação em mapas até recomendações em redes sociais.

Insights de Modelagem: Grafo do Espaço de Estados

Ao resolver enigmas lógicos (como o problema das jarras), cadaestado válidoé um vértice, e cadaação válidaé uma aresta. Resolver o problema consiste em encontrar um caminho do vértice inicial ao vértice-alvo.

Desafio de Modelagem Lógica: Problema das Jarras (Tarefa Escrita)

Mapear estados lógicos para uma estrutura de grafo

Você possui duas jarras com capacidades de 4 galões e 3 galões, respectivamente, sem marcações. Você pode enchê-las com uma bomba, esvaziá-las ou transferir água entre elas. Objetivo: deixar exatamente 2 galões na jarra de 4 galões.

编写一个程序或描述其建模逻辑以解决此问题。 (要求：输出不少于 150 字的逻辑描述或代码实现)

Resposta:
模型方案： 1. 顶点定义：使用元组 (v4, v3) 表示状态，其中 v4 为 4加仑坛子的水量，v3 为 3加仑坛子的水量。初始顶点为 (0,0)，目标顶点为 (2, x)。 2. 边定义：合法的操作（灌满、倒空、转移）构成边。例如 (0,0) -> (4,0) 是“灌满4加仑”的操作。 3. 解决步骤： - (0,0) -> (0,3) : 灌满3加仑 - (0,3) -> (3,0) : 倒入4加仑坛子 - (3,0) -> (3,3) : 再次灌满3加仑 - (3,3) -> (4,2) : 灌满4加仑坛子，此时3加仑坛子剩下2加仑 - (4,2) -> (0,2) : 倒空4加仑坛子 - (0,2) -> (2,0) : 将3加仑坛子中的2加仑倒入4加仑坛子，达成目标。

Modelagem de Cena: Gazelas e Leões Cruzando o Rio (Tarefa Escrita)

Busca de Caminho sob Restrições

Três gazelas e três leões estão prestes a atravessar um rio, com uma embarcação que suporta apenas dois animais. Se, em qualquer margem, o número de leões for maior que o de gazelas, as gazelas serão devoradas. Encontre uma forma segura de atravessar.

Descreva a modelagem do problema como um grafo e apresente uma trajetória viável. (Requisito: texto com pelo menos 120 palavras.)

Resposta:
建模逻辑： 1. 状态表示：(A_left, L_left, boat_pos)，分别代表左岸羚羊数、狮子数和船的位置（0左1右）。 2. 约束条件：A_left == 0 或 A_left >= L_left，且右岸同样满足此条件。 3. 路径序列： - (3,3,0) -> (3,1,1) : 运2狮子到右岸 - (3,1,1) -> (3,2,0) : 回1狮子 - (3,2,0) -> (3,0,1) : 运剩下2狮子到右岸 - (3,0,1) -> (3,1,0) : 回1狮子 - (3,1,0) -> (1,1,1) : 运2羚羊到右岸 - (1,1,1) -> (2,2,0) : 回1羚羊1狮子 - (2,2,0) -> (0,2,1) : 运最后2羚羊到右岸 - (0,2,1) -> (0,3,0) : 回1狮子 - (0,3,0) -> (0,1,1) : 运2狮子到右岸 - (0,1,1) -> (0,2,0) : 回1狮子 - (0,2,0) -> (0,0,1) : 全员到达右岸。

Análise de Complexidade e Estrutura (Resposta Curta)

Fundamentos Teóricos de Algoritmos

分析 buildGraph 函数（根据代码清单 7-2）的时间复杂度。

Resposta:
buildGraph 的时间复杂度为 O(V + E)。其中 V 是顶点数量，E 是边（或词对关系）的数量。addVertex 操作是 O(1)，addEdge 操作涉及字典查找也是平均 O(1)，因此总时间与输入规模呈线性关系。

Com base na seguinte matriz de adjacência, desenhe a estrutura gráfica correspondente: A-B:7, A-C:5, A-F:1, B-D:7, B-E:3, C-B:2, C-F:8, D-E:2, E-D:5, F-C:1.

Resposta:
Descrição da estrutura do grafo: - Conjunto de vértices V = {A, B, C, D, E, F} - Conjunto de arestas direcionadas com peso E = { (A,B,7), (A,C,5), (A,F,1), (B,D,7), (B,E,3), (C,B,2), (C,F,8), (D,E,2), (E,D,5), (F,C,1) } Este é um grafo direcionado, pesado e com ciclos complexo.